Software applications often use state machines that interact by passing messages. A state machine is a software component that maintains data defining its state between inputs, e.g. messages from other state machines or from an operating system, and whose behavior at any given time in response to incoming input depends on its state. In telecommunications the inputs are typically received as asynchronous messages. The reason for the popularity of state machines lies in the fact that state automata have proven to be a powerful software engineering approach in implementation of signaling applications in telecommunications. Due to the message oriented nature of asynchronous signaling applications, it has been natural to implement these as state machines.
A state of a state machine accepts some set of messages. Each accepted message triggers a certain state transition. If a message not belonging to the set of accepted messages is received, it may be lost, although e.g. in telecommunications state machine applications it is typically possible to save messages in order to avoid losing them.
Each state maps to a certain set of state transitions. The state transitions contain the actual program statements to be executed. When a state transition is activated by a correct combination of the current state and received message, the statements contained in the transition will be executed. A transition function maps state-message pairs into state transitions. More than one pair may map into a same state transition which means that the same state transition may be active in multiple states.
A state machine type defines the transition function and contents of the state transitions of a state machine. A state machine type may be instantiated as a single state machine instance or as multiple state machine instances.
A single state machine is useful only in small applications. For implementing more complex applications, like e.g. telecommunications applications, it is useful to have a plurality of state machines working in concert. E.g. in a signaling application there may be allocated one state machine instance for every session, and there may be tens of thousands of sessions to be handled by the signaling application.
Thus to handle this processing demand state machine instances are typically executed in a multiprocessing environment by threads. The term thread is a well-known prior art-concept referring to an execution context that is independently scheduled, but shares a single address space with other threads.
However, having one operating system thread for each state machine instance is not technically feasible, because there may be many thousands of state machine instances and operating systems do not support such amounts of threads. For example, Linux sets a limit of 1024 threads per process. Also, context switches may be needed. The term context switch refers to an operation that an operating system uses to switch execution turns between processes and/or threads. Context switches are heavy and time consuming operations since the state of a process and/or thread having been executed needs to be saved in total, and correspondingly the state of a new process and/or thread to be executed needs to be restored before execution turns can be switched. These operations require a large amount of machine instructions which in turn consume clock cycles.
In prior art, these performance and system resource usage problems have been solved in various ways. For example, only a single thread may be used. However, this results in another problem in that, when a state machine instance run by the thread makes a blocking call, such as reads data from a disk file, all the state machine instances block.
Another solution is disclosed by U.S. Pat. No. 6,167,423 in which a mechanism called clique is provided. Multiple functionally similar state machines are grouped together and a thread is allocated for the whole group. Since the state machines to be grouped together are functionally similar, the state machines will communicate with each other frequently. Thus it is justified to allocate a common thread for the whole group as it will result in avoiding context switches.
However, as is obvious from the above, there are significant drawbacks to this mechanism. If a member of the group blocks, other members will also block. Further, to be useful the mechanism requires state machines functionally similar so that they may be grouped. This is rarely the case in actual implementations.
Thus there is an obvious need for an efficient solution providing concurrent operation of state machines in a computing system.